from typing import List

class Solution:
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        w_len = len(words)
        q_len = len(queries)
        words_pre = [0] * w_len
        for i in range(w_len):
            words_pre[i] = self.f(words[i])

        words_pre.sort()
        ans = [0] * q_len
        for i in range(q_len):
            ans[i] = w_len - self.lowerBound(words_pre, self.f(queries[i]))

        return ans

    def lowerBound(self, nums: List[int], target: int) -> int:
        left = -1
        right = len(nums)
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid
            else:
                left = mid
        return right

    def f(self, s: str) -> int:
        cnt = 0
        ch = 'z'
        for c in s:
            if c < ch:
                cnt = 1
                ch = c
            elif c == ch:
                cnt += 1
        return cnt


if __name__ == '__main__':
    s = Solution()
